package com.nanbei.graph;

import java.util.Arrays;
import java.util.List;

/**
 * @ClassDescription: Bellman-Ford 算法是一种用于计算单源最短路径的算法，
 *                      能够处理包含负权边的图
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/2 13:55
 */
public class BellmanFord {

    public static void main(String[] args) {

        // 负边情况
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.setEdges(Arrays.asList(new Edge(v2, 2), new Edge(v3, 1)));
        v2.setEdges(Arrays.asList(new Edge(v3, -2)));
        v3.setEdges(Arrays.asList(new Edge(v4, 1)));
        v4.setEdges(Arrays.asList());
        List<Vertex> graph = Arrays.asList(v1, v2, v3, v4);

        // 负环情况
        /*Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.setEdges(Arrays.asList(new Edge(v2, 2)));
        v2.setEdges(Arrays.asList(new Edge(v3, -4)));
        v3.setEdges(Arrays.asList(new Edge(v4, 1), new Edge(v1, 1)));
        v4.setEdges(Arrays.asList());
        List<Vertex> graph = Arrays.asList(v1, v2, v3, v4);*/

        bellmanFord(graph, v1);
    }

    private static void bellmanFord(List<Vertex> graph, Vertex v1) {
        v1.setDist(0);
        // 如果有N个顶点 则进行N-1次循环来遍历节点更新节点的值,N-1论过后所有值即为最新
        // 第N轮循环用来检查图中是否含有负环
        for (int i = 0; i < graph.size()+1; i++) {
            // 遍历所有节点
            for (Vertex vertex : graph) {
                int dist = vertex.getDist();
                List<Edge> edges = vertex.getEdges();
                // 遍历节点的所有临边
                for (Edge edge : edges) {
                    Vertex linked = edge.getLinked();
                    int weight = edge.getWeight();
                    // 如果当前节点不为无穷大，并且新的距离小于当前距离则更新距离
                    if (dist != Integer.MAX_VALUE && (dist + weight) < linked.getDist()) {
                        if (i == graph.size()){
                            throw new RuntimeException("当前图中含有负环");
                        }
                        linked.setDist(dist + weight);
                        linked.setPerv(vertex);
                    }
                }
            }
        }

        for (Vertex vertex : graph) {
            System.out.println(vertex.getName() + " " + vertex.getDist() + " " + (vertex.getPerv()==null ? "null" : vertex.getPerv().getName()));
        }
    }
}
